/**
 * 堆是一颗完全二叉树
 * [10  9  8  5  6   7  4  3]
 * arr[0]
 * 10   0   【1，2】  
 * 9  1  【3， 4】  
 * 8  2   【5， 6 】
 * 在最底层之外 都是 满节点 1 + 2 + 4 + 8  = 2*i
 * 第i节点   2*i + 1
 * 1. 左子树节点的位置 
 * 2. 右子树节点的位置  2*i+ 2
 * 3. 父亲节点位置
 *  (i-1) / 2
 */
 import {ICompareFunction,defaultCompare, Compare } from '../../util/util'

 export class MinHeap<T> {
     protected heap: T[];
     constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
         this.heap = [];
     }
     protected getLeftIndex(index: number):number {
         return 2 * index + 1;
     }
     protected getRightIndex(index: number):number {
         return 2 * index + 2;
     }
     protected getParentIndex(index: number):number | undefined {
         if (index == 0) {
             return undefined;
         }
         return Math.floor((index - 1) / 2)
     }   
     //         1
     //    2       6
     //  5                         
     insert(value: T) :boolean{
         if (value != null) {
             // 先放到最后面 
             // 违反堆的定义 
             this.heap.push(value);
             this.shiftUp(this.heap.length - 1)
             return true;
         }
         return false;
     }
     protected shiftUp(index: number): void {
         let parent = <number>this.getParentIndex(index)
         while(index > 0 
             && 
             this.compareFn(this.heap[parent], this.heap[index])
             === Compare.BIGGER_THEN    
         ) {
             this.swap(this.heap, parent, index)
             parent = <number>this.getParentIndex(index)
         }
     }
     protected swap(array: T[], exchangeElement: number, 
         exchangedElement:number): void {
             const temp = array[exchangeElement]
             array[exchangeElement] = array[exchangedElement];
             array[exchangedElement] = temp;
         }
 }
 
 export class MaxHeap<T> extends MinHeap<T> {
 
 }
 